package io.adrainty.algorithm.leetcode.normal;

import java.util.Arrays;
import java.util.List;

/**
 * @author adrainty
 * @version v1.0.0
 * @since 2024/12/23 下午2:06
 */

@SuppressWarnings("unused")
public class Solution89 {

    private boolean flag = false;

    public List<Integer> grayCode(int n) {
        if (n == 0) return List.of();
        int size = (int) Math.pow(2, n);
        boolean[] isVisited = new boolean[size];
        int[] nums = new int[size];
        isVisited[0] = true;
        dfs(1, size, isVisited, nums);
        return Arrays.stream(nums).boxed().toList();
    }

    private void dfs(int cur, int n, boolean[] isVisited, int[] nums) {
        if (cur == n) {
            flag = true;
            return;
        }
        if (flag) return;
        for (int i = 1; i < n; i++) {
            if (isVisited[i]) continue;
            if ((cur == n - 1) && ((i & (i - 1)) != 0)) continue;
            int pre = nums[cur - 1];
            int tmp = pre ^ i;
            if ((tmp & (tmp - 1)) != 0) continue;
            nums[cur] = i;
            isVisited[i] = true;
            dfs(cur + 1, n, isVisited, nums);
            isVisited[i] = false;
            if (flag) return;
        }
    }

}
